package YuanFuDao2;


import java.util.Stack;

/**
 * 用两个栈实现排序栈
 */
public class Main1 {
    public static void main(String[] args) {
        SortedStack s = new SortedStack();
        s.push(2);
        s.push(4);
        s.push(1);
        s.push(6);
        System.out.println(s.peek());
    }
}

class SortedStack {

    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();  // 辅助栈

    public SortedStack() {

    }

    public void push(int val) {
        while(!s2.empty() && s2.peek() > val){  //辅助栈中存在比val大的值
            s1.push(s2.pop());
        }
        while(!s1.empty() && s1.peek() < val){  //原栈中有比val小的值
            s2.push(s1.pop());
        }
        s1.push(val);
    }

    public void pop() {
        while(!s2.empty()){
            s1.push(s2.pop());
        }

        if(!s1.empty()){
            s1.pop();
        }
    }

    public int peek() {
        while(!s2.empty()){ // 清空辅助栈
            s1.push(s2.pop());
        }
        if(!s1.empty()) return s1.peek();
        return -1;
    }

    public boolean isEmpty() {
        return s1.empty() &&  s2.empty();
    }
}
